<?php

class CliParser
{
	const IDSTRING = '([a-z]([a-z0-9_]*[a-z0-9])?)';
	const RPNCHAR = '@';
	const SEPARATOR = ';';
	const TERMINATOR = '()';

	private $mode;
	private $pos;
	private $inputMode;

	private $opPatterns;
	private $cmdPattern;

	private static $cmdchars = array(
		'/' => '',
		'.' => 'help',
	);

	public function __construct (CliMode $mode)
	{
		$this->mode = $mode;
		$this->pos = 0;
		$this->inputMode = false;

		$this->buildCmdPattern();
		$this->buildOpPatterns();
	}

	public function buildCmdPattern ()
	{
		$chars = array_keys(self::$cmdchars);
		foreach ($chars as $key => $char)
		{
			$chars[$key] = preg_quote($char, '/');
		}
		$this->cmdPattern = '/^\s*(' . implode('|', $chars) . ')/';
	}

	public function buildOpPatterns ()
	{

		$groups = array(ExpOperator::OP_PREFIX, ExpOperator::OP_OTHER);

		// Separate patterns are needed for each operator type
		foreach ($groups as $group)
		{
			$pattern = '';
			$operators = array();
			$singles = '';

			foreach ($this->mode->getOperators($group) as $op)
			{
				$len = strlen($op);

				// Ignore named operators
				if (preg_match('/^' . self::IDSTRING . '$/', $op))
				{
					continue;
				}
				elseif ($len == 1)
				{
					$singles .= preg_quote($op, '-');
				}
				else
				{
					$operators[preg_quote($op, '-')] = $len;
				}
			}

			arsort($operators);
			$keys = array_keys($operators);
			$keys[] = "[$singles]";

			$this->opPatterns[$group] = '-^(' . implode('|', $keys) . ")-";
		}
	}

	public static function getDefaultCommandChar ()
	{
		$keys = array_keys(self::$cmdChars);
		return $keys[0];
	}

	public function getNumber ($string)
	{
		$this->pos = 0;
		$number = $this->parseNumber($string);

		if ($string != '')
		{
			return false;
		}

		return $number;
	}

	public function parseInput ($input)
	{
		$this->inputMode = true;
		$this->pos = 0;
		$input = (string) $input;
		$length = strlen($input);
		$statements = array();

		try
		{
			// Parse statements until parser increments position to the end
			while ($this->pos < $length)
			{
				$stmt = $this->parseStatement(substr($input, $this->pos));

				if ($stmt !== null)
				{
					$statements[] = $stmt;
				}
			}
		}
		catch (CliParseException $ex)
		{
			$this->inputMode = false;
			throw $ex;
		}

		$this->inputMode = false;

		return $statements;
	}

	public function parseStatement ($string)
	{
		// Return null if the string consists of nothing but whitespace
		$EOS = $this->inputMode
			? '($|' . preg_quote(self::SEPARATOR, '/') . ')' : '$';

		if ($this->parse("/^\s*($EOS)/", $string))
		{
			return null;
		}

		// If the string matches the command input, it's a command
		if (preg_match($this->cmdPattern, $string))
		{
			$stmt = $this->parseCommand($string);
		}
		else
		{
			$stmt = $this->parseExpression($string);
		}

		return $stmt;
	}

	public function parseCommand ($cmd)
	{
		// Reset parsing position, if not called inside input mode
		if (!$this->inputMode)
		{
			$this->pos = 0;
		}

		// Determine how statement ends depending we are in input mode
		$EOS = $this->inputMode
			? '($|(?=' . preg_quote(self::SEPARATOR, '/') . '))'
			: '$';

		// Get the command character
		$char = $this->parse($this->cmdPattern, $cmd, 1);

		if ($char === false)
		{
			$this->parseTrim($cmd);
			$cmdchar = isset($cmd[0]) ? $cmd[0] : '';
			$this->error("Undefined command character '$cmdchar'");
		}

		// Determine the command by shortcut or by written text
		if (self::$cmdchars[$char] != '')
		{
			$command = self::$cmdchars[$char];
			$this->parseTrim($cmd);
		}
		else
		{
			$command = (string) $this->parse('/^(' . self::IDSTRING . ')/', $cmd);

			// Command must be followed by whitespace
			if ($this->parse("/^(\s+|($EOS))/", $cmd) === false)
			{
				$this->error("Unexpected character '$cmd[0]', expecting " .
					"whitespace or EOS");
			}
		}

		$args = array();

		$type = $this->mode->getIdentifierType($command);

		// Allow setting shortcut, if it's a setting
		if ($type === CliMode::ID_SETTING)
		{
			$args[] = $command;
			$command = 'set';
		}
		elseif ($type !== CliMode::ID_COMMAND)
		{
			$this->error("Unknown command or setting '$command'");
		}

		// Parse parameters until end of statement
		while (!preg_match("/^($EOS)/", $cmd))
		{
			// Determine parse method by first character in the parameter
			switch ($cmd[0])
			{
				// Single or double qutoe indicates quoted string
				case '"':
				case "'":
					// Parse a quoted string with quote escaping
					if ($arg = $this->parseQuotedString($cmd))
					{
						$args[] = $arg;
					}
					else
					{
						$this->error('Unclosed quoted parameter');
					}

					break;

				// Opening curly brace indicates an expression parameter
				case '{':
					$args[] = $this->parseInline($cmd);
					break;

				// Otherwise, just take all nonwhitespace as a string
				default:
					// Or number, if it works out
					if ($arg = $this->parseNumber($cmd))
					{
						$args[] = $arg;
					}
					else
					{
						$args[] = $this->parse('/^[^\s]+/', $cmd);
					}
			}

			// Each argument must be separated by whitespace
			if ($this->parse("/^(\s+|($EOS))/", $cmd) === false)
			{
				$this->error("Unexpected character '$cmd[0]', expecting " .
					"whitespace or EOS");
			}
		}

		// Remove statement separator
		if ($this->inputMode)
		{
			$this->parse('/^' . preg_quote(self::SEPARATOR, '/') . '/', $cmd);
		}

		return new CommandStmt($command, $args, $this->mode);
	}

	public function parseExpression ($exp, $inline = false)
	{
		// Reset parsing position if not doing it in input or inline mode
		if (!$this->inputMode && !$inline)
		{
			$this->pos = 0;
		}

		$EOS = $inline ? '($|\})' : ($this->inputMode
			? '($|' . preg_quote(self::SEPARATOR, '/') . ')'
			: '$');

		// Perform left trimming
		$this->parseTrim($exp);

		// Parse as RPN, if started with RPN char
		if ($this->parse('/^' . preg_quote(self::RPNCHAR, '/') . '/', $exp))
		{
			return $this->parseRPN($exp, $inline);
		}

		$queue = array();
		$stack = array();

		// Expressions always start with value
		$isValue = true;

		while (!preg_match("/^($EOS)/", $exp))
		{
			if ($isValue)
			{
				// ############ Matching in Value context ############

				// Attempt to parse number
				if (($tok = $this->parseNumber($exp)) !== false)
				{
					$queue[] = $tok;
				}
				// Function call (and included left parenthesis)
				elseif ($tok = $this->parse('/^(' . self::IDSTRING . ')(?=\s*\()/', $exp, 1))
				{
					$type = $this->mode->getIdentifierType($tok);
					if ($type === CliMode::ID_FUNCTION)
					{
						$this->parse('/^\s*\(/', $exp);
						$stack[] = new ExpFunction($tok, $this->mode);
						$queue[] = new StackTerminator();
					}
					// But it could actually be an operator too
					elseif ($type === CliMode::ID_OPERATOR)
					{
						$this->stackOperator($tok, ExpOperator::OP_PREFIX, $stack, $queue);
					}
					// Or maybe it's just a userfunction
					else
					{
						$this->parse('/^\s*\(/', $exp);
						$stack[] = new ExpUserfunc($tok);
						$queue[] = new StackTerminator();
					}

					$isValue = false;
				}
				// Left parenthesis (for forcing precedence)
				elseif ($this->parse('/^\(/', $exp))
				{
					$stack[] = '(';
					$isValue = false;
				}
				// Prefix operators
				elseif ($tok = $this->parse($this->opPatterns[ExpOperator::OP_PREFIX], $exp))
				{
					$this->stackOperator($tok, ExpOperator::OP_PREFIX, $stack, $queue);
					$isValue = false;
				}
				// Constants, variables and named operators
				elseif ($tok = $this->parse('/^(' . self::IDSTRING . ')/', $exp))
				{
					// It's operator if one exists with that name
					if ($this->mode->operatorExists($tok, ExpOperator::OP_PREFIX))
					{
						$this->stackOperator($tok, ExpOperator::OP_PREFIX, $stack, $queue);
						$isValue = false;
					}
					else
					{
						$queue[] = new ExpVariable($tok, $this->mode);
					}
				}
				// Beginning of an inline expression
				elseif ($tok = $this->parseInline($exp))
				{
					$queue[] = $tok;
				}
				// Also accept quoted strings
				elseif (($tok = $this->parseQuotedString($exp)) !== false)
				{
					$queue[] = $tok;
				}
				else
				{
					$this->errorToken($exp, 'value');
				}
			}
			else
			{
				// ############ Matching in Operator context ############

				// Parse all operators
				if ($tok = $this->parse($this->opPatterns[ExpOperator::OP_OTHER], $exp))
				{
					$op = $this->stackOperator($tok, ExpOperator::OP_OTHER, $stack, $queue);

					// If it's a postfix operator, operator should follow
					if ($op->argCount() == 1)
					{
						$isValue = true;
					}
				}
				// Right parenthesis
				elseif ($this->parse('/^\)/', $exp))
				{
					$next = array_pop($stack);

					while($next !== '(' && !($next instanceof ExpFunction))
					{
						$next = $this->nextStack($next, $stack, $queue, ')');
					}

					// Only put functions in the queue, no need for parenthesis
					if ($next instanceof ExpFunction)
					{
						$queue[] = $next;
					}

					// Closing parenthesis should be followed by operator
					$isValue = true;
				}
				// Function argument separator
				elseif ($this->parse('/^,/', $exp))
				{
					$next = array_pop($stack);

					while (!($next instanceof ExpFunction))
					{
						$next = $this->nextStack($next, $stack, $queue, ',');
					}

					// Put the function back in stack, since we're not done yet
					$stack[] = $next;
				}
				// Array index ending parenthesis
				elseif ($this->parse('/^\]/', $exp))
				{
					$next = array_pop($stack);

					while (!($next instanceof ExpOperator) || !$next->isArrayOperator())
					{
						$next = $this->nextStack($next, $stack, $queue, ']');
					}

					$queue[] = $next;

					// Right parenthesis is followed by operator
					$isValue = true;
				}
				// Named operator
				elseif ($tok = $this->parse('/^(' . self::IDSTRING . ')/', $exp))
				{
					$op = $this->stackOperator($tok, ExpOperator::OP_OTHER, $stack, $queue);

					// If it's a postfix operator, operator should follow
					if ($op->argCount() == 1)
					{
						$isValue = true;
					}
				}
				else
				{
					$this->errorToken($exp, 'operator');
				}
			}

			// Remove any excess whitespace
			$this->parseTrim($exp);
			$isValue = !$isValue;
		}

		// If isValue is true, we are missing a value at the end
		if ($isValue)
		{
			$this->error('Unexpected end, expecting a value');
		}

		// Inline expressions must end with }
		if ($inline)
		{
			if ($this->parse('/^\}/', $exp) === false)
			{
				$this->error('Unexpected end, expecting closing expression');
			}
		}
		// Remove possible statement separators
		else
		{
			$this->parse("/^($EOS)/", $exp);
		}

		// Any operator that is still left is in the stack is dumped in queue
		foreach (array_reverse($stack) as $op)
		{
			if ($op instanceof ExpOperator && $op->isArrayOperator())
			{
				$this->error("Unexpected end, expecting ']'");
			}
			if ($op === '(' || $op instanceof ExpFunction)
			{
				$this->error("Unexpected end, expecting ')'");
			}

			$queue[] = $op;
		}

		return new ExpressionStmt($queue);
	}

	private function nextStack ($item, & $stack, & $queue, $check)
	{
		if ($item === null)
		{
			$this->error("Unexpected '$check', no proper context");
		}
		if ($item === '(')
		{
			$this->error("Unexpected '$check', expecting ')'");
		}
		if ($item instanceof ExpFunction)
		{
			$this->error("Unexpected '$check', expecting ')'");
		}
		if ($item->isArrayOperator())
		{
			$this->error("Unexpected '$check', expecting ']'");
		}

		$queue[] = $item;
		return array_pop($stack);
	}

	private function stackOperator ($op, $group, &$stack, &$queue)
	{
		if (!$this->mode->operatorExists($op, $group))
		{
			$this->error("Unknown operator '$op'");
		}

		$o1 = new ExpOperator($op, $group, $this->mode);

		for ($o2 = end($stack); $o2 instanceof ExpOperator; $o2 = end($stack))
		{
			if ($o1->getAssoc() == ExpOperator::ASSOC_LEFT)
			{
				if ($o1->getPrec() <= $o2->getPrec())
				{
					$queue[] = array_pop($stack);
					continue;
				}
			}
			else
			{
				if ($o1->getPrec() < $o2->getPrec())
				{
					$queue[] = array_pop($stack);
					continue;
				}
			}

			break;
		}

		$stack[] = $o1;
		return $o1;
	}

	private function parseRPN ($exp, $inline)
	{
		$queue = array();
		$this->parseTrim($exp);

		$EOS = $inline ? '($|\})' : ($this->inputMode
			? '($|' . preg_quote(self::SEPARATOR, '/') . ')'
			: '$');

		$terminatorPattern = '/^' . preg_quote(self::TERMINATOR, '/') . '/';

		while (!preg_match("/^($EOS)/", $exp))
		{
			// Quoted strings are parsed as strings
			if ($tok = $this->parseQuotedString($exp))
			{
				$queue[] = $tok;
			}
			// Stack terminators are taken from the queue
			elseif ($this->parse($terminatorPattern, $exp))
			{
				$queue[] = new StackTerminator();
			}
			// Attempt to parse the number
			elseif (($tok = $this->parseNumber($exp)) !== false)
			{
				$queue[] = $tok;
			}
			// Parse inline expressions
			elseif ($tok = $this->parseInline($exp))
			{
				$queue[] = $tok;
			}
			// Parse function tokens separately from other identifiers
			elseif ($tok = $this->parse('/^(' . self::IDSTRING . ')\(/', $exp, 1))
			{
				$type = $this->mode->getIdentifierType($tok);

				if ($type === false)
				{
					$queue[] = new ExpUserfunc($tok);
				}
				elseif ($type === CliMode::ID_FUNCTION)
				{
					$queue[] = new ExpFunction($tok, $this->mode);
				}
				else
				{
					$this->error("Unexpected token type for '$tok', expected function");
				}
			}
			// Otherwise take all nonwhitespace and check what it is
			elseif (($tok = $this->parse('/^[^\s\};]+/', $exp)) !== false)
			{
				$type = $this->mode->getIdentifierType($tok);

				// If the token has no known type, it's probably a variable
				if ($type === false)
				{
					// And variables must match the ID string definition
					if (preg_match('/^' . self::IDSTRING . '$/', $tok))
					{
						$queue[] = new ExpVariable($tok, $this->mode);
					}
					else
					{
						$this->error("Unknown RPN token '$tok'");
					}
				}
				elseif ($type === CliMode::ID_OPERATOR)
				{
					$queue[] = $this->mode->getOperatorByName($tok);
					break;
				}
				elseif ($type === CliMode::ID_CONSTANT)
				{
					$queue[] = new ExpVariable($tok, $this->mode);
					break;
				}
				else
				{
					$this->error("Unexpected token type for '$tok', expected variable or operator");
				}
			}
			else
			{
				$this->errorToken($exp, 'token');
			}

			$tok = $this->parseTrim($exp);

			// All tokens must be separated by whitespace
			if ($tok === false && !preg_match("/^($EOS)/", $exp))
			{
				$this->error("Unexpected character '$exp[0]', expected whitespace");
			}
		}

		// Inline expressions must end with }
		if ($inline)
		{
			if ($this->parse('/}/', $exp) === false)
			{
				$this->error('Unexpected end, expecting closing expression');
			}
		}
		// Remove possible statement separators
		else
		{
			$this->parse("/^($EOS)/", $exp);
		}

		return new ExpressionStmt($queue, !$this->inputMode);
	}

	private function parse ($regexp, & $string, $sub = 0)
	{
		if (!preg_match($regexp, $string, $match))
		{
			return false;
		}

		$length = strlen($match[0]);

		if ($length > 0)
		{
			$string = substr_replace($string, '', 0, $length);
			$this->pos += $length;
		}

		return $match[$sub];
	}

	private function parseNumber (& $string)
	{
		// Fail fast if, if the next token can not be a number
		if (!preg_match('/^[-+.\d]/', $string))
		{
			return false;
		}

		// Normal integer numbers
		if (($tok = $this->parse('/^[-+]?(0(?![\dx.e])|[1-9](?>\d*)(?!\.|e))/', $string)) !== false)
		{
			return $this->mode->getInt($tok);
		}
		// Float representation of a decimal (with scientific notation)
		elseif ($tok = $this->parse('/^[-+]?(0(?!\d|x)|[1-9]\d*)?(?=\.|e)(\.\d+)?(?<=\d)(e[-+]?\d+)?/', $string))
		{
			return $this->mode->getFloat($tok);
		}
		// Octal representation of an integer
		elseif ($tok = $this->parse('/^0([0-7]+)/', $string, 1))
		{
			return $this->mode->getInt($this->stringBaseConvert($tok, '01234567'));
		}
		// Hexadecimal representation of an integer
		elseif ($tok = $this->parse('/^0x([0-9a-f]+)/', $string, 1))
		{
			return $this->mode->getInt($this->stringBaseConvert($tok, '0123456789abcdef'));
		}

		return false;
	}

	private function parseTrim (& $string)
	{
		return $this->parse('/^\s+/', $string);
	}

	private function parseQuotedString (& $string)
	{
		// Try to parse quoted string with escaping
		$text = $this->parse(
			'/^((")|\')((?>(?:[^\'"\\\\]+|\\\\.|(?(2)\'|"))*))\1/s',
			$string, 3);

		// Return false if nothing was found
		if ($text === false)
		{
			return false;
		}

		// Parse escaped quotes and escape characters
		$text = preg_replace('/(?<!\\\\)\\\\((?:\\\\\\\\)*)([\'"])/','$1$2', $text);
		$text = str_replace('\\\\', '\\', $text);

		return $text;
	}

	private function parseInline (& $string)
	{
		if (!$this->parse('/^\{/', $string))
		{
			return false;
		}

		$now = $this->pos;
		$expression = $this->parseExpression($string, true);
		$string = $this->pos - $now === strlen($string)
			? '' : substr($string, $this->pos - $now);

		return $expression;
	}

	private function stringBaseConvert ($numstring, $frombase, $tobase = '0123456789')
	{
		$from_count = strlen($frombase);
		$to_count = strlen($tobase);
		$length = strlen($numstring);
		$result = '';

		for ($i = 0; $i < $length; $i++)
		{
			$number[$i] = strpos($frombase, $numstring[$i]);
		}

		// Loop until whole number is converted
		do
		{
			$divide = 0;
			$newlen = 0;

			// Perform division manually
			for ($i = 0; $i < $length; $i++)
			{
				$divide = $divide * $from_count + $number[$i];
				if ($divide >= $to_count)
				{
					$number[$newlen++] = (int) ($divide / $to_count);
					$divide = $divide % $to_count;
				}
				elseif ($newlen > 0)
				{
					$number[$newlen++] = 0;
				}
			}

			$length = $newlen;
			$result = $tobase[$divide] . $result;
		}
		while ($newlen > 0);

		return $result;
	}

	private function error ($msg)
	{
		throw new CliParserException("$msg (at {$this->pos})");
	}

	private function errorToken ($exp, $next)
	{
		preg_match('/^(\w+|[^\w\s]*)/', $exp, $match);
		$this->error("Unexpected token '$match[0]', expected '$next'");
	}
}

?>